//===----------------------------------------------------------------------===//
//
//                         CMU-DB Project (15-445/645)
//                         ***DO NO SHARE PUBLICLY***
//
// Identification: src/page/b_plus_tree_internal_page.cpp
//
// Copyright (c) 2018, Carnegie Mellon University Database Group
//
//===----------------------------------------------------------------------===//

#include <exception>
#include <iostream>
#include <sstream>
#include <utility>

#include "common/exception.h"
#include "common/macros.h"
#include "storage/page/b_plus_tree_internal_page.h"
#include "storage/page/b_plus_tree_leaf_page.h"
#include "storage/page/b_plus_tree_page.h"

namespace bustub {
/*****************************************************************************
 * HELPER METHODS AND UTILITIES
 *****************************************************************************/
/*
 * Init method after creating a new internal page
 * Including set page type, set current size, and set max page size
 */
INDEX_TEMPLATE_ARGUMENTS
void B_PLUS_TREE_INTERNAL_PAGE_TYPE::Init(int max_size) {
  this->SetMaxSize(max_size);
  // 暂时先让size为0
  this->SetSize(0);
  this->SetPageType(IndexPageType::INTERNAL_PAGE);
  //
}
/*
 * Helper method to get/set the key associated with input "index"(a.k.a
 * array offset)
 */
INDEX_TEMPLATE_ARGUMENTS
auto B_PLUS_TREE_INTERNAL_PAGE_TYPE::KeyAt(int index) const -> KeyType {
  // replace with your own code
  // 暂时不做index和size的判断
  BUSTUB_ASSERT(index < this->GetMaxSize(), "B_PLUS_TREE_INTERNAL_PAGE_TYPE::KeyAt : index大于最大容量\n");
  return array_[index].first;
}

INDEX_TEMPLATE_ARGUMENTS
void B_PLUS_TREE_INTERNAL_PAGE_TYPE::SetKeyAt(int index, const KeyType &key) {
  BUSTUB_ASSERT(index < GetMaxSize(), "B_PLUS_TREE_INTERNAL_PAGE_TYPE::KeyAt : index大于最大容量\n");
  array_[index].first = key;
}

/*
 * Helper method to get the value associated with input "index"(a.k.a array
 * offset)
 */
INDEX_TEMPLATE_ARGUMENTS
auto B_PLUS_TREE_INTERNAL_PAGE_TYPE::ValueAt(int index) const -> ValueType { return array_[index].second; }

INDEX_TEMPLATE_ARGUMENTS
auto B_PLUS_TREE_INTERNAL_PAGE_TYPE::ValueIndex(const ValueType &value) const -> int {
  int size = GetSize();
  for (int i = 0; i < size; ++i) {
    if (array_[i].second == value) {
      return i;
    }
  }
  return -1;
}

INDEX_TEMPLATE_ARGUMENTS
auto B_PLUS_TREE_INTERNAL_PAGE_TYPE::Search(KeyType key, KeyComparator &comparator) const -> int {
  int mid = -1;
  int start = 1;
  int end = this->GetSize() - 1;
  while (start < end) {
    mid = (start + end) / 2;
    if (comparator(key, array_[mid].first) != -1) {
      start = mid + 1;
    } else {
      end = mid;
    }
  }
  BUSTUB_ASSERT(start == end, "start != end");
  return comparator(key, array_[start].first) == -1 ? start : -1;
}

INDEX_TEMPLATE_ARGUMENTS
void B_PLUS_TREE_INTERNAL_PAGE_TYPE::PushBack(const KeyType &key, const ValueType &value) {
  array_[GetSize()] = std::make_pair(key, value);
  IncreaseSize(1);
}
INDEX_TEMPLATE_ARGUMENTS
void B_PLUS_TREE_INTERNAL_PAGE_TYPE::Truncate(int length) { this->SetSize(length); }

INDEX_TEMPLATE_ARGUMENTS
void B_PLUS_TREE_INTERNAL_PAGE_TYPE::Insert(int pos, const KeyType &key, const ValueType &value) {
  // BUSTUB_ASSERT(pos >= 1, "pos==0! use PushBack to add the first element!");
  BUSTUB_ASSERT(GetSize() < GetMaxSize(), "page is full!");
  for (int i = GetSize(); i >= pos + 1; --i) {
    array_[i] = array_[i - 1];
  }
  array_[pos] = std::make_pair(key, value);
  this->IncreaseSize(1);
}

INDEX_TEMPLATE_ARGUMENTS
void B_PLUS_TREE_INTERNAL_PAGE_TYPE::Delete(const KeyType &key, const KeyComparator &comparator) {
  int mid = -1;
  int start = 1;
  int end = this->GetSize();
  while (start < end) {
    mid = (start + end) / 2;
    if (comparator(key, array_[mid].first) != -1) {
      start = mid + 1;
    } else {
      end = mid;
    }
  }
  BUSTUB_ASSERT(start == end, "start != end");
  start--;
  BUSTUB_ASSERT(start >= 1, "没找到key");
  BUSTUB_ASSERT(comparator(key, array_[start].first) == 0, "没找到key");
  for (int i = start; i < GetSize() - 1; ++i) {
    array_[i] = array_[i + 1];
  }
  IncreaseSize(-1);
}

INDEX_TEMPLATE_ARGUMENTS
void B_PLUS_TREE_INTERNAL_PAGE_TYPE::Delete(int index) {
  if (index < 0 || index >= this->GetSize()) {
    throw bustub::Exception("index越界");
  }
  for (; index < this->GetSize() - 1; ++index) {
    array_[index] = array_[index + 1];
  }
  IncreaseSize(-1);
}

// valuetype for internalNode should be page id_t
template class BPlusTreeInternalPage<GenericKey<4>, page_id_t, GenericComparator<4>>;
template class BPlusTreeInternalPage<GenericKey<8>, page_id_t, GenericComparator<8>>;
template class BPlusTreeInternalPage<GenericKey<16>, page_id_t, GenericComparator<16>>;
template class BPlusTreeInternalPage<GenericKey<32>, page_id_t, GenericComparator<32>>;
template class BPlusTreeInternalPage<GenericKey<64>, page_id_t, GenericComparator<64>>;
}  // namespace bustub
